package com.bupt.dp;

/**
 * 动态规划问题
 * 
 * @author feng
 *
 */
// lcs问题方向枚举变量
enum char_direct {
	init, leftUp, left, up
};

public class DPAlgorithm {

	/**
	 * 最长递增子序列
	 * O（N2）解法
	 * @param int[] a 
	 * @return
	 */
	public int lis(int[] a) {
		int len = 1;
		int[] d = new int[a.length];
		d[0] = 1;
		for (int i = 1; i <= a.length - 1; i++) {
			d[i] = 1;
			for (int j = 0; j <= i - 1; j++) {
				if (a[i] > a[j] && d[j] + 1 > d[i]) {
					d[i] = d[j] + 1;
				}
			}
			if (d[i] > len)
				len = d[i];
		}
		return len;
	}
	/**
	 * 最长递增子序列 O（Nlg2N）解法
	 * @param a
	 * @return
	 */
	public int list2(int[] a){
		int[] B = new int[a.length];
		B[1] = a[0];
		int right = 1;
		for(int i = 1; i<a.length ;i++){
			if(a[i] > B[right]){
				right++;
				B[right] = a[i];
			}else {
				int low = 1;
				int high = right;
				while(low <= high) {
					int mid = (low + high)/2;
					if(a[i]<a[mid]){
						high = mid -1;
					}else {
						low = mid +1 ;
					}
				}
				B[low] = a[i];
			}
		}
		return right;
	}
	/**
	 * 数塔取数问题
	 * 一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
	 * http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1002
	 * @param tower
	 * @return int
	 */
	public int NumberTowerProblems(int[][] tower){
		int max = tower[0][0];
		int[][] d = new int[tower.length][];
		d[0] = new int[tower[0].length];
		d[0][0] = tower[0][0];
		for(int i = 1; i<tower.length;i++){
			d[i] = new int[tower[i].length];
			for(int j = 0;j<tower[i].length;j++ ){
				int up1 = j>0?d[i-1][j-1]:0;
				int up2 = j<tower[i].length-1?d[i-1][j]:0 ;
				d[i][j] = up1>up2?up1+tower[i][j]:up2+tower[i][j];
				if(d[i][j] > max) {
					max = d[i][j];
				}
			}
		}
		return max;
	}
	/**
	 * 最长公共子序列,动态规划经典例题
	 * @param A
	 * @param B
	 * @return
	 */
	public String longestCommonSubsequence(char A[], char B[]) {
		int lenA = A.length;
		int lenB = B.length;
		int[][] b = new int[lenA][];
		char_direct[][] dir = new char_direct[lenA][];
		// 初始化
		for (int i = 0; i < lenA; i++) {
			b[i] = new int[lenB];
			b[i][0] = 0;
		}
		for (int j = 0; j < lenB; j++) {
			b[0][j] = 0;
		}
		// 方向矩阵初始化
		for (int i = 0; i < lenA; i++) {
			dir[i] = new char_direct[lenB];
			for (int j = 0; j < lenB; j++) {
				dir[i][j] = char_direct.init;
			}
		}
		// 动态规划算法
		for (int i = 0; i < lenA; i++) {
			for (int j = 0; j < lenB; j++) {
				// 第一行与第一列的情况
				if (i == 0 || j == 0) {
					if (A[i] == B[j]) {
						b[i][j] = 1;
						dir[i][j] = char_direct.leftUp;
					} else {
						if (i > 0) {
							b[i][j] = b[i - 1][j];
							dir[i][j] = char_direct.up;
						}
						if (j > 0) {
							b[i][j] = b[i][j - 1];
							dir[i][j] = char_direct.left;
						}
					}
				} else if (A[i] == B[j]) {
					b[i][j] = b[i - 1][j - 1] + 1;
					dir[i][j] = char_direct.leftUp;
				} else if (b[i - 1][j] >= b[i][j - 1]) {
					b[i][j] = b[i - 1][j];
					dir[i][j] = char_direct.up;
				} else {
					b[i][j] = b[i][j - 1];
					dir[i][j] = char_direct.left;
				}
			}
		}
		StringBuffer s = new StringBuffer();
		printLogestCommonSubsequence(dir, A, B, lenA-1, lenB-1, s);
		return s.toString();
	}

	/**
	 * 递归获得最长公共子序列
	 * 
	 * @param A
	 * @param B
	 * @param b
	 * @param dir
	 */
	public void printLogestCommonSubsequence(char_direct[][] dir, char A[],
			char[] B, int row, int col, StringBuffer lcs) {
		if (A.length == 0 || B.length == 0) {
			return;
		}
		if (!(row < A.length && row >= 0 && col >=0 && col < B.length)) {
			return;
		}
		if (dir[row][col] == char_direct.leftUp) {
			printLogestCommonSubsequence(dir, A, B, row - 1, col - 1, lcs);
			lcs.append(A[row]);
		} else if (dir[row][col] == char_direct.left) {
			if (col > 0)
				printLogestCommonSubsequence(dir, A, B, row, col - 1, lcs);
		} else {
			if (row > 0)
				printLogestCommonSubsequence(dir, A, B, row - 1, col, lcs);
		}
	}
	
	public int PositiveIntegerGroup(int []a){
		int result = Integer.MAX_VALUE;
		int total = 0;
		for(int i = 0 ; i < a.length ;i++){
			total += a[i];
		}
		return result;
	}
	
}
